\documentclass{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
%\usepackage{ctex}
\usepackage{listings}
\usepackage{subfigure}


% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\usepackage{xcolor}
\usepackage{fontspec} 
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{comment}{rgb}{0.56,0.64,0.68}

\newfontfamily\monaco{Monaco}
\lstset {
aboveskip=3mm,
belowskip=3mm,
showstringspaces=false,       % underline spaces within strings
columns=flexible,
framerule=1pt,
rulecolor=\color{gray!35},
backgroundcolor=\color{gray!5},
basicstyle={\small\monaco},           % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\tiny\monaco\color{gray},  % the style that is used for the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
commentstyle=\color{comment},
keywordstyle=\color{blue},
stringstyle=\color{dkgreen},
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
escapeinside={\%*}{*)},            % if add LaTeX within your code
morekeywords={*,...}               % if add more keywords to the set
}


\begin{document}
\title{Homework \#3}
\pagestyle{fancy}
\lhead{Name Li HuiTeng 3180102114}
\chead{ numPDE\#3}
\rhead{Date 21.05.10}


\tableofcontents

\newpage


\section{8.14 Practice three FD formulas, deduce orders of accuracy and give a geometric interpretation.}
\begin{proof}[Proof]
	Apply the formula $lim_{h \to 0}log_2\frac{\varepsilon (2h)}{\varepsilon (h)}=p$ to deduce the accuracy.
	The results are produced by MATLAB R2019b.
	\lstset{language=Matlab}
	\begin{lstlisting}
%This is a file named calculate_.m .
function [E1,E2,E3] = calculate_(h)
True=cos(1);
E1=(sin(1.0+h)-sin(1.0))/h-True;
E2=(sin(1.0)-sin(1.0-h))/h-True;
E3=(sin(1.0+h)-sin(1.0-h))/(2*h)-True;
end

%This is a file named pro8_14.m .
[E(1,1),E(2,1),E(3,1)]=calculate_(0.01);
[E(1,2),E(2,2),E(3,2)]=calculate_(0.005);
p_rough=zeros(3,1);
for i=1:3
   p_rough(i)= log2(abs(E(i,1)))-log2(abs(E(i,2)));
end
fprintf("%s\n",'Error Table')
fprintf("%8s %6s %15s %15s %15s\n",'','h','FD1','FD2','FD3');
fprintf("%8s %6s %15.6e %15.6e %15.6e\n",'','0.01',E(1,1),E(2,1),E(3,1));
fprintf("%8s %6s %15.6e %15.6e %15.6e\n",'','0.005',E(1,2),E(2,2),E(3,2));
fprintf("%s\n",'Rough Accuracy')
fprintf("%8s %15s %15s %15s\n",'','FD1','FD2','FD3');
fprintf("%8s %15.3e %15.3e %15.3e\n",'',p_rough(1),p_rough(2),p_rough(3));

%This is the input and the output of Terminal.
>> pro8_14
Error Table
              h             FD1             FD2             FD3
           0.01   -4.216325e-03    4.198315e-03   -9.004993e-06
          0.005   -2.105924e-03    2.101422e-03   -2.251257e-06
Rough Accuracy
                     FD1             FD2             FD3
               1.002e+00       9.984e-01       2.000e+00
\end{lstlisting}
	As the above calculation shows, it's much more likely that the first two formulas have order 1
	while the third has order 2.

	Actually these formulas are based on the same idea : approximating tangent with secant.
	The geometric interpretation is shown below.
	\begin{center}
		\includegraphics[width=0.7\textwidth]{geogebra-export.png}
	\end{center}
\end{proof}

\section{8.15 Prove orders of accuracy for the above three FD formulas.}
\begin{proof}[Proof]
	Expand $u(x+h),u(x-h)$ at x:
	\begin{align*}
		u(x+h) & =u(x)+hu'(x)+\frac{h^2}{2}u''(x)+\frac{h^3}{6}u'''(x)
		+\frac{h^4}{24}u^{(4)}(x)+O(h^5),                              \\
		u(x-h) & =u(x)-hu'(x)+\frac{h^2}{2}u''(x)-\frac{h^3}{6}u'''(x)
		+\frac{h^4}{24}u^{(4)}(x)+O(h^5).
	\end{align*}
	Thus,
	\begin{align*}
		E_1 & =D_+u(x)-u'(x)=u'(x)+\frac{h}{2}u''(x)+O(h^2)-u'(x)=\Theta (h),     \\
		E_2 & =D_-u(x)-u'(x)=u'(x)-\frac{h}{2}u''(x)+O(h^2)-u'(x)=\Theta (h),     \\
		E_3 & =D_0u(x)-u'(x)=u'(x)+\frac{h^2}{3}u'''(x)+O(h^4)-u'(x)=\Theta(h^2).
	\end{align*}
\end{proof}

\section{8.16 Derive a quadratic polynomial and obtain the FD formula from taking derivative.}
\begin{proof}[Proof]
	Construct the table of divided difference as below.
	\[	\begin{array}{c|ccc}\overline x&f(\overline x)&&\\\overline x-h&f(\overline x-h)&\frac{f(\overline x)-f(\overline x-h)}h&\\\overline x-2h&f(\overline x-2h)&\frac{f(\overline x-h)-f(\overline x-2h)}h&\frac{f(\overline x)-2f(\overline x-h)+f(\overline x-2h)}{2h^2}\end{array}
\]
Hence, 
\begin{align*}
	p(x)&=f(\overline x)+\frac{f(\overline x)-f(\overline x-h)}h(x-\overline x)+\frac{f(\overline x)-2f(\overline x-h)+f(\overline x-2h)}{2h^2}(x-\overline x)(x-\overline x+h).\\p'(x)&=\frac{f(\overline x)-f(\overline x-h)}h+\frac{f(\overline x)-2f(\overline x-h)+f(\overline x-2h)}{2h^2}(2x-2\overline x+h).\\p'(\overline x)&=\frac{3f(\overline x)-4f(\overline x-h)+f(\overline x-2h)}{2h},
\end{align*}
which corresponds to the FD formula.
\end{proof}

\section{8.20 Show the differences in the max-norm, 1-norm and 2-norm.}
\begin{proof}[Proof]
	When h inclines to 0,
	\begin{align*}
		\frac{||g||_{\infty}}{h} & =max|g_i/h|\leq max\{C_1,C_N\}\Rightarrow ||g||_{\infty}=O(h),                                                       \\
		||g||_1                  & =h\big((N-2)O(h^2)+2O(h)\big)=h\big((T/h-2)O(h^2)+O(h)\big)=h\big(O(h)\big)=O(h^2),                                  \\
		||g||_2                  & =\bigg(h\big((N-2)O(h^4)+2O(h^2)\big)\bigg)^{0.5}=\big(O(h^4)+2O(h^3))\big)^{0.5}=\big(O(h^3)\big)^{0.5}=O(h^{1.5}),
	\end{align*}
	where $C_1,C_N$ are from $g_1 \leq C_1h$, $g_N \leq C_Nh$, and $T=h\cdot N$ is a constant.
\end{proof}

\section{8.44 Show the first column of $B_E$ contains elements that are $O(1)$.}
\begin{proof}[Proof]
	Denote the first column of $B_E$ by $X$.
	Then $A_E X=e_1$, and we have
	\[
		\begin{pmatrix}-h&h&&&&&\\1&-2&1&&&&\\&1&-2&1&&&\\&&\ddots&\ddots&\ddots&&\\&&&1&-2&1&\\&&&&1&-2&1\\&&&&&0&h^2\end{pmatrix}\begin{pmatrix}x_{m+1}\\x_m\\\vdots\\\vdots\\x_2\\x_1\\x_0\end{pmatrix}=\begin{pmatrix}h^2\\0\\0\\\vdots\\0\\0\\0\end{pmatrix}
	\]
	Solve the equations, and 
	\[ 
	x_k=-kh,\quad k=0,1,\cdots,m+1.
	\]
	Since $(m+1)h=T=1$, every $|x_k|$ is bounded by 1. We conclude that X contains elements that are O(1).
\end{proof}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
